Một nhà ngoại giao Nga đã gặp ông ở Thụy Điển và mời ông phục vụ quân đội Nga trong thời gian 3 năm, khởi đầu với quân hàm thiếu tá. Gordon chấp nhận và rồi, khi đến Moskva, mới biết thời gian quy định trong hợp đồng không có nghĩa lý gì cả: vì là sĩ quan, ông không được phép ra đi. Khi ông xin đi, bên Nga dọa sẽ kết án ông làm gián điệp cho Ba Lan và có thể đày ông đi Siberia. Sau thời gian tạm thời chấp nhận số phận của mình, ông hòa nhập vào cuộc sống tại Moskva. Nhanh chóng hiểu ra rằng cơ hội tốt nhất để thăng tiến là cưới một phụ nữ Nga, ông tìm được một người, rồi tạo dựng một gia đình.

Nhiều năm trôi qua, ông đã phục vụ Sa hoàng Aleksei I (cha của Pyotr), Sa hoàng Fyodor III (anh cùng cha khác mẹ của Pyotr) và Phụ chính Sofia Alekseyevna (chị cùng cha khác mẹ của Pyotr). Ông tham gia vào các trận chiến chống Ba Lan, các sắc tộc Thổ, Tatar và Bashkir. Ông được thăng lên cấp tướng và đã về thăm Anh và Scotland hai lần, sau khi người Nga đảm bảo nhân vật sáng giá này sẽ trở lại bằng cách giữ vợ con ông ở lại Moskva.

Năm 1686, vua James II của Anh đích thân yêu cầu Sofia chấm dứt nhiệm vụ của ông ở Nga để ông có thể về nước; Sofia từ chối, và trong một thời gian có thêm lời nói bóng gió về việc tiêu tan sự nghiệp và Siberia. Rồi James II gửi công văn thông báo muốn bổ nhiệm Gordon làm đại sứ ở Moskva; việc đề cử lại bị từ chối vì ông vẫn còn ở trong quân ngũ và sắp lên đường đi chinh chiến chống Tatar. Thế là, vào năm 1689, ở tuổi 54, được mọi người kính trọng, Gordon trở nên cực kỳ giàu có (lương 1000 rúp mỗi năm, trong khi lương của giáo sĩ Lutheran chỉ có 60), và là một nhân vật nổi danh ở Khu Ngoại ô Đức.